#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 斐波那契数
// 斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列
// 该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。
// 也就是：F(0) = 0，F(1) = 1
// F(n) = F(n - 1) + F(n - 2)，其中 n > 1
// 给定 n ，请计算 F(n)

// 递归实现
int fib1(int n)
{
    if (n == 0)
    {
        return 0;
    }
    if (n == 1)
    {
        return 1;
    }
    return fib1(n - 1) + fib1(n - 2);
}

// 记忆化搜索实现
int f2(int i, vector<int> &dp)
{
    if (i == 0)
    {
        return 0;
    }
    if (i == 1)
    {
        return 1;
    }
    if (dp[i] != -1)//说明展开过了
    {
        return dp[i];
    }
    int ans = f2(i - 1, dp) + f2(i - 2, dp);
    dp[i] = ans;
    return ans;
}

int fib2(int n)
{
    //缓存表
    vector<int> dp(n + 1, -1);
    return f2(n, dp);
}

// 动态规划实现
int fib3(int n)
{
    if (n == 0)
    {
        return 0;
    }
    if (n == 1)
    {
        return 1;
    }
    vector<int> dp(n + 1);
    dp[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

// 空间优化动态规划实现
int fib4(int n)
{
    if (n == 0)
    {
        return 0;
    }
    if (n == 1)
    {
        return 1;
    }
    int lastLast = 0, last = 1;
    for (int i = 2, cur; i <= n; i++)
    {
        cur = lastLast + last;
        lastLast = last;
        last = cur;
    }
    return last;
}

int main()
{
    int n = 10; // 示例输入
    cout << "fib1: " << fib1(n) << endl;
    cout << "fib2: " << fib2(n) << endl;
    cout << "fib3: " << fib3(n) << endl;
    cout << "fib4: " << fib4(n) << endl;
    return 0;
}
